package LeetCode_1_100;

class Solution05 {
    public String longestPalindrome(String s) {
        StringBuilder sb = new StringBuilder("^#");
        for (char c : s.toCharArray()) {
            sb.append(c).append('#');
        }
        sb.append('$');
        String T = sb.toString();

        int n = T.length();
        int[] P = new int[n];
        int C = 0, R = 0;

        for (int i = 1; i < n-1; i++) {
            int mirror = 2 * C - i;
            if (i < R) P[i] = Math.min(R - i, P[mirror]);

            // 扩展回文
            while (T.charAt(i + P[i] + 1) == T.charAt(i - P[i] - 1)) {
                P[i]++;
            }

            // 更新中心和右边界
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }

        // 找出最大回文
        int maxLen = 0, center = 0;
        for (int i = 1; i < n-1; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                center = i;
            }
        }
        int start = (center - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }
}

public class LeetCode05_longestPalindrome {
    public static void main(String[] args) {
        Solution05 solution = new Solution05();
        String s;

        //Case 1
        s = "babad";
        System.out.println(s);
        System.out.println(solution.longestPalindrome(s));

        //Case 2
        s = "cbbd";
        System.out.println(s);
        System.out.println(solution.longestPalindrome(s));
    }
}
